package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/5 11:03
 *
 * 判断栈的压入弹出顺序是否合理
 */

import java.util.Stack;

public class Main13 {
    public  boolean IsPopOrder(int [] pushA,int [] popA) {
        int i=0,j=0;
        Stack<Integer>stack=new Stack<>();
        while (i<pushA.length){
            if(stack.isEmpty()||stack.peek()!=popA[j]){
                stack.push(pushA[i++]);
            }
            //使用while是因为i到了最后的时候，栈中可能有多个元素
            while (!stack.empty()&&stack.peek()==popA[j]){
                //栈顶=出栈
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
    //数组模拟栈
    public  boolean IsPopOrder2(int [] pushA,int [] popA){
        //栈顶指针
        int top=0;
        int j=0;
        //遍历入栈
        for(int e:pushA){
            pushA[top++]=e;
            //栈非空且相等就弹出
            while (top>0&&pushA[top]==popA[j]){
                top--;
                j++;
            }
        }
        return top==0;
    }
    public static void main(String[] args) {
        int pushA[]={1,2,3,4,5};
        int popA[]={4,3,5,1,2};
        //int popA[]={4,5,3,2,1};
        Main13 main13=new Main13();
        System.out.println(main13.IsPopOrder(pushA,popA));
    }
}
